package codingforgreat.class04;

import java.util.*;

public class Class08_TheSkylineProblem {

    class Node {
        public int x;
        public boolean isAdd;
        public int h;

        public Node(int x, boolean isAdd, int h) {
            this.x = x;
            this.isAdd = isAdd;
            this.h = h;
        }
    }

    public List<List<Integer>> getSkyline(int[][] buildings) {
        Node[] nodes = new Node[buildings.length * 2];
        int index = 0;
        for (int[] building : buildings) {
            nodes[index++] = new Node(building[0], true, building[2]);
            nodes[index++] = new Node(building[1], false, building[2]);
        }
        Arrays.sort(nodes, (Node o1, Node o2) -> {
            return o1.x == o2.x ? o1.isAdd ? -1 : 1 : o1.x - o2.x;
        });
        List<List<Integer>> res = new ArrayList<>();
        //key -> h  value -> times
        TreeMap<Integer, Integer> heihtTimes = new TreeMap<>();
        LinkedHashMap<Integer, Integer> mapXHeight = new LinkedHashMap<>();
        for (int i = 0; i < nodes.length; i++) {
            if (nodes[i].isAdd) {
                if (!heihtTimes.containsKey(nodes[i].h)) {
                    heihtTimes.put(nodes[i].h, 1);
                } else {
                    heihtTimes.put(nodes[i].h, heihtTimes.get(nodes[i].h) + 1);
                }
            } else {
                heihtTimes.put(nodes[i].h, heihtTimes.get(nodes[i].h) - 1);
                if (heihtTimes.get(nodes[i].h) == 0) {
                    heihtTimes.remove(nodes[i].h);
                }
            }
            if (heihtTimes.isEmpty()) {
                mapXHeight.put(nodes[i].x, 0);
            } else {
                mapXHeight.put(nodes[i].x, heihtTimes.lastKey());
            }
        }
        mapXHeight.forEach((x, h) -> {
            if (res.isEmpty() || res.get(res.size() - 1).get(1) != h) {
                res.add(new ArrayList<>(Arrays.asList(x, h)));
            }
        });
        return res;
    }
}
